1. Technical Field
The present invention relates to signal processing. More specifically, the invention relates to methods and systems for determining a representation of a signal.
2. Related Art
Compressive sampling is a method to simultaneously sample and compress a signal. Traditional methods for capturing and processing of signals firstly sample the signal and secondly compress the sampled data. According to the Nyquist criteria, in case the signal to be sampled is bandlimited, the sampling should be carried out above the Nyquist frequency, which is twice the frequency range of the signal. If the sampling is followed by compression, e.g. JPEG of image, a lot of redundant information is eliminated from the data sampled before.
It turned out that these two steps can be performed in one, thereby allowing obtaining compressed data with far less samples. As a result, it becomes possible to sample very high bandwidth signals or to obtain accuracy with fewer sensors. Applications for compressive sampling are widespread and include audio and image processing from the development of cameras, medical image devices and security scanners to new algorithms to record and sample audio and video. In all applications, a reduction of power consumption and/or an increase in efficiency can be obtained.
One of the core tenets of compressive sampling is the notion of incoherence. Two bases are said to be incoherent if signals with a sparse support in one are guaranteed to be spread out when expressed in the other. This property is crucial for compressive sampling. For a pair of given bases the incoherence can be measured quantitatively. The highest incoherent pair of bases has been shown to play a role in obtaining a high amount of information for few samples.
In E. J. Candès and M. Wakin: “An introduction to compressive sampling”, IEEE Signal Processing Magazine, 25:21-30, March 2008, a method for compressive sampling is also described.
Therefore, there are situations which require constructing a pair of perfectly incoherent bases (a pair of bases with the highest incoherence between them).
Wavelets are well known in the field of harmonic analysis and signal processing. Apart from their fundamental significance they have been widely employed in various industry standard applications. For instance, the JPEG 2000 standard uses the Cohen-Daubechies-Feauveau wavelet transform to achieve image compression. Wavelets naturally appear as the sparsity basis in compressive sampling and are widely promoted. Hardware applications often favor the discrete Haar wavelet, which is computationally simple and the use of which results in comparable or even better performance than more sophisticated wavelets in lots of applications (see e.g. T. Tuma, S. Rooney, P. Hurley: “On the applicability of compressive sampling for fine grained processor performance monitoring”, ICECCS 2009, Potsdam, Germany).
The present invention generally relates to compressive sampling which can be performed in a computationally efficient manner with a minimal amount of samples needed. In particular, the invention also relates to a fast algorithm which allows for transforming a signal into a domain which is perfectly incoherent with a Haar domain. This means that compressive sampling can be used with a Haar domain as the sparsity basis at its best performance.
Fast transforms are crucial for practicality of any sampling ensemble. It can be realized that one way to obtain the data in a domain perfectly incoherent with a Haar domain is to convert the data to a Haar domain and subsequently, apply a Hadamard transform. However, a straightforward implementation using the two transforms separately, explicitly results in twice as many computational stages as one can expect of a fast transform.
Other approaches to obtain a perfectly or maximally incoherent basis to a Haar basis are known, e.g. by R. Coifman, F. Geshwind and Y. Meyer, “Noiselets”, Applied and Computational Harmonic Analysis, 10:27-44, 2001. Therein, a fast noiselet transform can be implemented based on the Cooley-Tukey design pattern. However, noiselets are complex by definition. This means that the transform algorithm and result inherently use and produce complex numbers. Without any other processing taken into account this means a double effort in software and in hardware, respectively, which is expensive in most of the application domains.
It is therefore an object of the present invention to provide a method for converting a signal using a fast and efficient algorithm which allows transforming a signal into a domain which is perfectly incoherent with a Haar domain, and which consists solely of real numbers.